package leetcode.pre50;

/**
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @date 2020/3/23 16:00
 */
public class Code04_FindMedianInSortedArr {

    /**
     * 方式1：时间O(m+n),空间O(m+n)，外排
     *
     * 奇数下：len-1/2 == len/2为中间那个
     * 偶数下：len-1 /2是中间靠前，len/2是中间靠后。
     * 所以可以中位数可以统一写成 avrage(len-1/2 + len/2)
     */

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        Double x = doubleCheck(nums1,nums2);
        if(x != null) return x;
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        int a[] = new int[len];
        int p1 = 0;
        int p2 = 0;
        int index = 0;
        while (p1 < len1 && p2 < len2) {
            a[index++] = nums1[p1] < nums2[p2] ? nums1[p1++] : nums2[p2++];
        }
        while (p1 < len1) a[index++] = nums1[p1++];
        while (p2 < len2) a[index++] = nums2[p2++];
        //奇数偶数统一
        return a[(len-1)/2] + a[len/2]/2.0 ;
    }

    /**
     * 方式2：也是基于快排，但是不需要真正地排，只需要做标记。
     *
     */
    public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        Double x = doubleCheck(nums1,nums2);
        if(x != null) return x;
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        //总索引数，从0开始计算，当到达(len1+len2)/2时，就是after。
        int aimIndex = 0;
        //记录len-1/2处元素
        int before = Math.min(nums1[0],nums2[0]);
        ////记录len/2处元素
        int after = before;
        int p1 = 0;
        int p2 = 0;
        while (p1 < len1 && p2 < len2){
            //把before更新为after，因为after要从新更新了
            after = nums1[p1] < nums2[p2] ? nums1[p1++] : nums2[p2++];
            if(aimIndex++ == len / 2){
                return (len & 1) == 0? (after + before) / 2.0 :
                        after;
            }
            before = after;

        }
        while (p1 < len1){
            after = nums1[p1++];
            if(aimIndex++ == len/ 2){
                return (len & 1) == 0? (after + before) / 2.0 :
                        after;
            }
            before = after;
        }
        while (p2 < len2){
            after = nums2[p2++];
            if(aimIndex++ == len / 2){
                return (len & 1) == 0? (after + before) / 2.0 :
                        after;
            }
            before = after;
        }
        return -1;
    }

    /**
     * 方式3：二分法。对两个数组找中位数。假设总长度len为奇数，就是找第len/2位置的数，
     * 换言之就是找第 k = len/2+1小的数。
     * 所以直接比较num1与num2中各自 k/2位置的数。如果num1的小于num2的，那么num1的0-k/2都比num2[k/2]小，
     * 所以排除掉k/2个。剩余len - k/2个数中，找第k-k/2小的数，在此基础上递归上述过程。
     */
    public static double findMedianSortedArrays2(int[] nums1, int[] nums2){
        Double x = doubleCheck(nums1,nums2);
        if(x != null) return x;
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        //奇数个数，找len/2或者len-1/2位置，  也就是找第len/2 + 1小的数
        if((len & 1) == 1){
            return getK(nums1,0,len1-1,nums2,0,len2-1,len/2+1);
        }
        //偶数个数，找len/2与len-1/2位置，然后取均值
        //也就是第 len/2+1小和第len-1/2+1小的数
        return (
                getK(nums1,0,len1-1,nums2,0,len2-1,len/2+1) +
                getK(nums1,0,len1-1,nums2,0,len2-1,(len-1)/2+1)
                )/2.0;
    }

    //在两个数组中找第k小的数
    private static int getK(int[]nums1,int start1,int end1,
                            int[]nums2,int start2,int end2,
                            int k){
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        if(len1 <= 0){
            return nums2[start2 + k - 1];
        }
        if(len2 <= 0){
            return nums1[start1 + k - 1];
        }
        //注意k == 1，这时候 k/2 = 0，nums[0 + k/2 - 1]越界
        if(k == 1){
            return Math.min(nums1[start1],nums2[start2]);
        }
        //找第k/2小的数，对应索引是 start + k/2 - 1，但是要注意 k/2不能超过len1
        //如len1最大是100，那么最大也就是找第100的数，此时k == 200
        int i = start1 + Math.min(len1,k/2) - 1;
        int j = start2 + Math.min(len2,k/2) - 1;
        //start1 - i 所有的数都比nums2[j]小
        if(nums1[i] < nums2[j]){
            return getK(nums1,i+1,end1,nums2,start2,end2,k - (i - start1 + 1));
        }else {
            return getK(nums1,start1,end1,nums2,j+1,end2,k - (j - start2 + 1));
        }

    }

    private  static Double doubleCheck(int[] num1,int []num2){
        if(num1 == null && num2 == null || num1.length == 0 && num2.length == 0)
            throw new RuntimeException("illegal input ");
        int len1 = num1.length;
        int len2 = num2.length;
        //get median nums2.奇数偶数统一
        if(num1 == null || num1.length == 0)
            return (num2[(len2-1)/2] + num2[len2/2])/2.0;
        if(num2 == null || num2.length == 0)
            return  (num1[(len1-1)/2] + num1[len1/2])/2.0;
        return null;//合法
    }
    public static void main(String[] args) {
        int[] a1 = {1,3,4};
        int[] a2 = {2};
        System.out.println(findMedianSortedArrays2(a1, a2));
    }
}
